The present invention relates to a block placement method for automatically placing a plurality of blocks on a substrate, such as a printed wiring board and a substrate of a large scale integrated (LSI) circuit.
Conventionally, the block placement method uses the placement cells of m rows and n columns (m, n:integer, m.gtoreq.2, n.gtoreq.2) defined on a substrate for the blocks to be placed. The conventional placement method employing the initial placement and its improvement is described in an article by Gary Robson, entitled "Automatic Placement and Routing of Gate Arrays", VLSI DESIGN, pp.35-43, April issue 1984 (referred as reference A in the following).
According to the reference A, it is assumed that any block of arbitrary size can freely be located on some cells among mxn cells defined on a substrate. However, there are ground and power line areas on the substrate, on which the usual block cannot be placed. In other words, the block of its size larger than the distances between ground or power lines cannot be placed. For example, the block for the so-called hardmacro, which is a kind of circuit designed to place and connect hardware elements, corresponds to this case. Therefore, the locations of the ground and power lines are previously searched and the blocks to be placed are extended so as to bestride those ground and power lines.
Therefore, since the locations of the power and ground lines have already been determined, the placement location of the block should be determined beforehand to provide the extended block on the basis of calculation of the relative positions of the power and ground lines followed by the actual provision of the extended block in consideration of the disposed power and ground lines.
Consequently, the various extended blocks must be provided, since the locations of the power and ground lines are different for each block. Moreover, the location of the extended blocks can hardly be moved in the placement improving step, because the locations of the power and ground lines within the block are fixed.